#include "base.h"

class Solution
{
public:
    const char *arr[8] = {
        "abc",
        "def",
        "ghj",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    };
    void recur(string digits, vector<string> &final, int depth)
    {
        auto index = (digits[depth] - '2');
        char *zm = (char *)arr[index];
        while (*zm)
        {
            auto &cur_str = final[final.size() - 1];
            if (digits.size() == depth + 1)
            {
                cur_str[depth] = *zm;
                cur_str.resize(depth + 1);
                final.push_back(cur_str);
            }
            else
            {
                cur_str[depth] = (*zm);
                recur(digits, final, depth + 1);
            }

            zm++;
        }
    }

    vector<string>
    letterCombinations(string digits)
    {
        if (digits.size() == 0)
        {
            return vector<string>();
        }
        vector<string> final = {digits};
        recur(digits, final, 0);

        return final;
    }
};

int main()
{
    auto a = Solution().letterCombinations("234");

    return 0;
}